#pragma once
#include "SomeTool.h"

template <size_t K>
struct VanEmdeBoasTreeBase
{
	static constexpr size_t u = PowN<2, PowN<2, K>>;

	std::optional<size_t> _pMin;
	std::optional<size_t> _pMax;

	auto min() const->std::optional<size_t> { return _pMin; }
	auto max() const->std::optional<size_t> { return _pMax; }

protected:
	bool insertEmpty(size_t x);
};

template <size_t K>
struct VanEmdeBoasTree : public VanEmdeBoasTreeBase<K>
{
	typedef VanEmdeBoasTreeBase<K> Base;
	typedef VanEmdeBoasTree<K - 1> Cld;

	Cld* _summary = NULL;
	Cld* _cluster[Cld::u] = {};

	bool member(size_t x) const;
	auto successor(size_t x) const->std::optional<size_t>;
	auto predecessor(size_t x) const->std::optional<size_t>;
	bool insert(size_t x);
	void erase(size_t x);

private:
	size_t high(size_t x) const { return x / Cld::u; }
	size_t low(size_t x) const { return x % Cld::u; }
	size_t index(size_t x, size_t offset) const { return x * Cld::u + offset; }
};

template <>
struct VanEmdeBoasTree<0> : public VanEmdeBoasTreeBase<0>
{
	typedef VanEmdeBoasTreeBase Base;

	bool member(size_t x) const;
	auto successor(size_t x) const->std::optional<size_t>;
	auto predecessor(size_t x) const->std::optional<size_t>;
	bool insert(size_t x);
	void erase(size_t x);
};

#include "VanEmdeBoasTreeImpl.h"
